package a_doubleWrite;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeMap;

/**
 * todo
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-03 09:50
 */
public class L729 {
    /* time:n^2
    private List<int[]> list;

    public L729() {
        list = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] n:list) {
            if(n[1]>start&&n[0]<end) return false;
        }
        list.add(new int[]{start, end});
        return true;
    }
    */
    //nlogn
    private TreeMap<Integer, Integer> treeMap;

    public L729() {
        treeMap = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        //获取小于等于start的key
        Integer prev = treeMap.floorKey(start);
        //大于等于
        Integer next = treeMap.ceilingKey(start);
        if ((prev == null || treeMap.get(prev) <= start)
                &&(next == null || end <= next)) {
            treeMap.put(start, end);
            return true;
        }
        return false;
    }
}
